package test2;

import java.math.BigInteger;

public class RabinDecryptor {
    public static BigInteger[] decrypt(BigInteger c, BigInteger p, BigInteger q) {
        BigInteger n = p.multiply(q);
        BigInteger mp = c.modPow(p.add(BigInteger.ONE).divide(BigInteger.valueOf(4)), p);
        BigInteger mq = c.modPow(q.add(BigInteger.ONE).divide(BigInteger.valueOf(4)), q);

        BigInteger[] result = new BigInteger[4];
        BigInteger[] extEuclid = extendedEuclid(p, q);
        BigInteger yp = extEuclid[1];
        BigInteger yq = extEuclid[2];

        result[0] = yp.multiply(p).multiply(mq).add(yq.multiply(q).multiply(mp)).mod(n);
        result[1] = n.subtract(result[0]);
        result[2] = yp.multiply(p).multiply(mq).subtract(yq.multiply(q).multiply(mp)).mod(n);
        result[3] = n.subtract(result[2]);

        return result;
    }

    private static BigInteger[] extendedEuclid(BigInteger a, BigInteger b) {
        if (b.equals(BigInteger.ZERO)) {
            return new BigInteger[]{a, BigInteger.ONE, BigInteger.ZERO};
        } else {
            BigInteger[] result = extendedEuclid(b, a.mod(b));
            BigInteger d = result[0];
            BigInteger x = result[2];
            BigInteger y = result[1].subtract(a.divide(b).multiply(result[2]));
            return new BigInteger[]{d, x, y};
        }
    }
}
